\section{Ejercicio 2}

Sea una matriz de enteros de $n \times m$, no vac\'ia, definimos meseta como el conjunto de celdas adyacentes sobre sus
lados que comparten un mismo valor. Hallar la cantidad de elementos de la meseta m\'as extensa. Resolver el problema en
$O((n \cdot m)2 )$.

\textbf{Entrada} \texttt{Tp1Ej2.in}

El archivo contiene varias instancias, y cada una consta de dos l\'ineas. La primera contiene dos enteros separados por
un blanco para n y m respectivamente. La segunda contiene todos los elementos de la matriz, separados entre si por un
blanco, siguiendo el orden natural de lectura.

\textbf{Salida} \texttt{Tp1Ej2.out}
Para cada instancia de entrada, se debe indicar una l\'inea con la cantidad de celdas que ocupa la meseta de mayor extensi\'on.

\subsection{Introducci\'on}

El ejercicio fue resuelto en menor complejidad temporal que la pedida. Propusimos e implementamos un algoritmo $O(n \cdot m)$,
ya que fue posible reducir el problema a encontrar la cantidad de v\'ertices en la componente conexa m\'as grande de un grafo,
problema de soluci\'on conocida mediante el algoritmo de exploraci\'on de grafos DFS (Depth-First Search).

\subsection{Desarrollo}

\subsubsection{Explicaci\'on del Algoritmo}

Lo que el algoritmo hace es, dada una celda $(i,j)$ cualquiera
de la matriz, encontrar el tama\~no de la meseta de tama\~no m\'aximo que contiene esa celda. La meseta 
que contiene una celda $(i,j)$ cualquiera es \'unica, puesto que consiste
en el grupo de todas las celdas continuas (pegadas por un lado) y contiguas que tienen el mismo valor que ella, como esta dado
por la definici\'on del enunciado. 

Siendo que la meseta que contiene a una celda es \'unica, podemos contar la cantidad de celdas que tiene ``expandiendonos'' desde la celda inicial, as\'i:
Una vez contada la celda, revisamos cada una de sus vecinas (es decir, el subconjunto de las celdas de arriba, abajo, izquierda y derecha que son v\'alidas
en la matriz). Si sus vecinas tienen el mismo valor, entonces lo que hacemos es repetir el mismo procedimiento en cada una de ellas. Lo que hacemos entonces es
b\'asicamente contar el tama\~no de cada meseta una \'unica vez, utilizando para ello un algoritmo recursivo.

Para asegurar que lo hacemos una \'unica vez, mantenemos que celdas ya fueron visitadas de manera de evitar visitar una
celda m\'as de una vez. Adem\'as de contar la celda en nuestro m\'etodo recursivo, tambi\'en marcamos la celda como visitada, y en el c\'odigo donde
revisamos las vecinas de una casilla, solo la visitamos si no fue ya visitada. Esto asegura primero que los c\'alculos sean correctos y segundo 
que el programa no se cuelgue infinitamente.

Para mejorar la claridad de esta explicaci\'on incluimos el siguiente pseudoc\'odigo:

\begin{algorithm}[H]
	\caption{Pseudoc\'odigo para combinar dos arreglos ordenados $A$ y $B$ en un 
	arreglo ordenado $C$.}
	\label{algo::contar_mesetas}
	\begin{algorithmic}
		\State \Var mesetaActual
		\State \Var mesetaMaxima

%		\State \Comment{contarMeseta: Dada una casilla $(i,j)$, calcula el tama\~no de la meseta m\'axima que la contiene, propagando recursivamente.}		
		\Function{contarMeseta}{tablero, celda $(i,j)$}

			\ForAll{$(p,q)$ $\in$ celdaVecinas(tablero,$(i,j)$)}

				\If{ valor(tablero,$(p,q)$) = valor(tablero,$(i,j)$) $\wedge \neg$ fueVisitada(tablero,$(p,q)$) }
				
%					\State \Comment{Esto quiere decir que la casilla $(p,q)$, al ser vecina de $(i,j)$ es parte de la meseta que contiene a $(p,q)$. La contamos
%					si no la hemos visitado anteriormente, y propagamos a sus vecinas no visitadas con igual valor (que son parte de la isla tambi\'en).}
					
					\State marcarVisitada(tablero, $(p,q)$)
					\State mesetaActual $\gets$ mesetaActual + 1 
				
%					\State \Comment{Continuo propagando desde esta casilla para calcular la meseta}
					\State contarMeseta($(p,q)$)
				\EndIf
			\EndFor
		\EndFunction

%		\State \Comment{resolver: Resuelve el ejercicio en si, llamando a contar para todas las casillas}
		\Function{resolver}{tablero}
			\State mesetaMaxima $\gets$ 0

			\ForAll{$(i,j)$ $\in$ casillas(tablero)}
				\If{$\neg$ visitada(tablero, $(i,j)$)}
%					\State \Comment{Si no visite esta casilla entonces su meseta no esta calculada. La calculo usando contar. }
					\State marcarVisitada(tablero,$(i,j)$)
					\State mesetaActual = 1
					\State valorActual = valor(tablero,$(i,j)$) %\Comment{En mesetaActual guardo el tama\~no del pedazo de meseta propagado, que al principio es una casilla. } 
				
					\State contar($(i,j)$)
					
%					\State \Comment{Ya terminamos de propagar la meseta de la casilla $(i,j)$.}
					\State mesetaMaxima $\gets \max$(mesetaMaxima, mesetaActual);
				\EndIf
			\EndFor
			
			\State \Return mesetaMaxima 

		\EndFunction
		
	\end{algorithmic}
\end{algorithm}

Para deducir la correctitud del algoritmo, consideremos la siguiente redefinici\'on de meseta:

\begin{definition}
	Una meseta m\'axima de una matriz $M$ es un conjunto $C$ de celdas tales que, $c,c' \in C$ si y solo si existe una secuencia
	$c = c_1, c_2, \dots, c_n = c'$ de celdas tales que $c_i$ y $c_{i+1}$ son directamente adyacentes (comparten un lado), $(\forall i) 1 \leq i \leq n$, y tales que
	$valor(c_i) = valor(c_j)$, $\forall  1 \leq i,j \leq n$. 
\end{definition}

Esta definici\'on es clara del enunciado: Una meseta consiste en las celdas adyacentes sobre sus lados que tienen el mismo valor, y tales
que no puedo agregar una celda que tambi\'en cumpla esta condici\'on.

Notemos tambi\'en que la definici\'on del enunciado implica la siguiente relaci\'on transitiva: Sean $c,c',c''$ tres celdas de la matriz.
Si $valor(c) = valor(c')$ y $valor(c') = valor(c'')$, entonces $valor(c) = valor(c'')$.

Veamos ahora como demostrar el siguiente

\begin{lemma}
	Toda celda $c$ de la matriz est\'a en una y solo una meseta de tama\~no m\'aximo.
\end{lemma}

\begin{proof}
	Para ver que toda casilla esta en al menos una meseta m\'axima, sea el conjunto $C$ el conjunto de todos los conjuntos $X$ de casillas tales
	que para dos celdas $c, c'$, $c, c' \in X$ solo si $c$ y $c'$ son adyacentes como est\'a explicado la definici\'on  de meseta m\'axima.
	
	(N\'otese que esto consiste en relajar la condici\'on de que sea si y solo si, es decir miramos todas las posibles mesetas y no solo la o las que 
	tenga tama\~no m\'aximo).  
	
	Es evidente que el conjunto $X' = { c }$ esta dentro de $C$, para toda celda $c$. Es obvio tambi\'en que para toda celda $c$, el conjunto $C$ correspondiente
	es finito (ya que esta contenido en el conjunto de subconjuntos de elementos de la matriz, que tiene una cantidad $2^{nm}$ de elementos). Por lo tanto,
	el conjunto $C$ contiene uno o m\'as conjuntos de cardinalidad m\'axima (es decir, donde la cantidad de elementos dentro del conjunto es m\'axima). 
	
	Con esto probamos que hay al menos una meseta m\'axima, puesto que cualquiera de estos posibles conjuntos de cardinalidad m\'axima contiene a todos las celdas
	adyacentes con $c$. Si no fuera as\'i, es decir hay una celda $c'$ tal que es adyancente con $c$ y no esta en $C$, entonces agregar esta casilla (lo cual podemos
	hacer por la transitividad de la noci\'on de adyacencia) aumentar\'ia
	la cantidad de elementos del conjunto, lo cual invalidar\'ia el si y solo si de la definici\'on de meseta m\'axima. 
	
	Con esto vemos que existe al menos una meseta m\'axima existe. Ahora veamos que es \'unica.
	
	Supongamos dos mesetas m\'aximas $C$ y $C'$ correspondientes a la celda $c$. 
	Probaremos que tienen los mismos elementos mediante una demostraci\'on de la doble inclusi\'on. Como la cardinalidad de ambos conjuntos es la misma,
	entonces podemos demostrar una sola de las inclusiones.
	
	Tenemos trivialmente que $c \in C$ y $c \in C'$, por ser las mesetas de la celda $c$.
		
	Queremos ver entonces que $(\forall c' \in C) c' \in C'$. Que $c' \in C$ implica que existe una secuencia $c' = c_0, c_1, \dots c_n = c$ tal que son todas adyacentes
	y tienen el mismo valor. Probaremos que para todo $c'' \in C'$, existe una secuencia $c' = c'_0 = \dots = c'_n = c''$ tal que son todas adyacentes entre si.
	Esta secuencia se obtiene sencillamente de la observaci\'on de que como $c \in C'$ implica que existe una secuencia $c = c''_0, c''_1, \dots, c''_n = c''$ tal que
	son todas adyacentes entre si. Definimos entonces la secuencia:
	
	\[
		c' = c_0, c_1, \dots , c_{n-1}, c''_0, c''_1, \dots c''_k = c''
	\]
	
	Con lo cual el hecho de que $c$ sea adyacente a $c''$ implica que $c' \in C'$, ya que entonces por transitividad es adyacente a todas las dem\'as en $C'$.
	
	Dado que la cardinalidad es la misma, al probar esta inclusi\'on probamos la igualdad de conjuntos. \qed
\end{proof}

A partir de este lema tenemos el siguiente

\begin{corollary}
	El algoritmo propuesto recorre al menos vez cada meseta.
\end{corollary}

El cual es inmediato del hecho de que el algoritmo recorre cada casilla de la matriz en el ciclo \texttt{for} dentro de la funci\'on \texttt{resolver}.

Veamos que el algoritmo recorre todos los valores de una meseta una vez.

\begin{lemma}
	Dada una celda $c$, el algoritmo \texttt{contar} recorre todos los elementos de la meseta m\'axima cuando se ejecuta empezando en la casilla $c$.
\end{lemma}

\begin{proof}
	El lema es inmediato de la definici\'on de meseta m\'axima, y la ejecuci\'on del algoritmo. El algoritmo se expande a las celdas adyacentes de la 
	celda $c$ que tienen el mismo valor, y recursivamente hace lo mismo con estas celdas adyacentes, marcando las celdas ya visitadas. Para ver el lema
	tenemos que ver que cada casilla dentro de la meseta m\'axima de $c$ es marcada al menos una vez, que ninguna celda que no pertenezca a la meseta
	m\'axima de $c$ es marcada, y que el algoritmo nunca marca una celda mas de una vez.
	
	Empecemos demostrando que toda celda de la meseta es marcada al menos una vez.
	
	Por la definici\'on, si $c'$ es una celda dentro de la
	meseta m\'axima de $c$, al existir una serie $c = c_0, c_1, \dots, c_n = c'$ tal que dos celdas $c_k, c_{k+1}$ son 
	directamente adyacentes $\forall 0 \leq k < n-1$ y $valor(c_i) = valor(c_j)$, $\forall 1 \leq i,j \leq n$, el
	algoritmo recursivamente va a visitar vecinas para recorrerlas al menos una vez. Vemos esto por inducci\'on en la longitud $n$ de la serie.
	
	\begin{itemize}
		\item $n = 1$. Si $n = 1$ entonces las celdas $c$ y $c'$ son directamente adyacentes (es decir comparten un lado). Por lo tanto, el ciclo \texttt{for} tdentro
		de \texttt{contar} encontrara esta celda dentro del conjunto de vecinas, ver\'a que tienen el mismo valor, 
		y si no esta marcada (lo cual pasa inicialmente) la marcar\'a. Por lo tanto, cada vecina de $c$ es marcada al menos una vez.
		\item $n \rightarrow n+1$. Puesto que son adyacentes y suponemos $n+1 > 1$ , $c_0$ y $c_1$ comparten un lado, por lo tanto el algoritmo marcar\'a al
		menos una vez $c_1$ y despu\'es se llamar\'a recursivamente sobre este. La secuencia $c_1, c_2, \dots, c_{n+1} = c' $ tiene longitud $n$, por lo tanto
		por hip\'otesis inductiva \texttt{correr} sobre $c_1$ marcar\'a al menos una vez la casilla $c'$, como quer\'iamos demostrar.
	\end{itemize} 
	
	Por otro lado, supongamos que $c'$ no esta en la meseta m\'axima de $c$. Entonces, porque la definici\'on de meseta m\'axima implica un si y solo si,
	no puede ocurrir que exista una secuencia $c = c_0, c_1, \dots, c_n = c'$ tal que sean directamente adyacentes de a pares consecutivos y todas tengan
	el mismo valor. Si el algoritmo \texttt{contar} hubiera en el proceso de hacer llamadas recursivas encontrado la celda $c'$, partiendo de $c$, entonces
	reconstruyendo la secuencia de llamadas tendr\'iamos que hay una secuencia como esta, puesto que el algoritmo solo se llama recursivamente con la celda $Y$,
	partiendo de la celda $X$, si $X$ e $Y$ tienen el mismo valor y son directamente adyacentes. Absurdo. Por lo tanto, el algoritmo nunca encontrar\'a una celda
	que no este dentro de la meseta m\'axima de $c$.
	
	Finalmente, para ver que cada celda es marcada una \'unica vez, veamos que si una celda se vuelve a encontrar y esta marcada entonces el algoritmo nunca
	vuelve a visitarla (la ignora). Como ya mostramos que a una celda $c'$ dentro de la meseta m\'axima de $c$ 
	debe poder llegarse siguiendo vecinas directamente adyacentes que tengan el mismo valor, nunca partiendo de contar de la celda $c$ podemos llegar a 
	la misma celda de la meseta m\'as de una vez. \qed
\end{proof}

Por lo tanto,

\begin{corollary}
	El algoritmo \texttt{contar} devuelve en \texttt{mesetaActual} la cantidad de celdas que pertenencen a la meseta m\'axima de la celda $c$
	que se esta examinando dentro del ciclo de \texttt{resolver}.
\end{corollary}

ya que por cada celda vecina a la que estamos mirando dentro de \texttt{contar} (que ya demostramos debe ser una celda que pertenece a la meseta m\'axima de la celda $c$ con la que
empezamos a propagar) incrementamos en uno este contador, y ponemos ese contador en uno (contamos la celda para la cual empezamos a propagar),
antes de empezar el ciclo. Por lo tanto hay una biyecci\'on entre los momentos en los que incrementamos el contador \texttt{mesetaActual} y las veces que
llamamos a \texttt{contar}.

Adem\'as tenemos que,

\begin{lemma}
	El ciclo for dentro de la funci\'on \texttt{resolver} no visita m\'as de una vez cada meseta m\'axima.
\end{lemma}

\begin{proof}
	Como ya demostramos que \texttt{contar} marca una \'unica vez todas las celdas de una meseta m\'axima, y toda celda esta si o si dentro de una \'unica meseta,
	entonces si esa celda cuando el ciclo for la encuentra no esta visitada, tiene que ocurrir que su meseta m\'axima todav\'ia no fue explorada. Al marcarla y 
	propagar llamando a la funci\'on \texttt{contar}, estamos marcando entonces marcando todas las celdas de su meseta m\'axima. Si cuando encontramos en el ciclo \texttt{for}
	a la celda, esta ya esta marcada, entonces quiere decir que su meseta m\'axima ya fue visitada y por lo tanto no debemos contarla de vuelta. \qed
\end{proof}

De este lema se desprende que

\begin{corollary}
	El algoritmo \texttt{resolver} recorre una \'unica vez la cantidad de v\'ertices de cada meseta m\'axima de la matriz. \qed
\end{corollary}

Finalmente podemos demostrar la correctitud del algoritmo.

\begin{lemma}
	En todo momento de la ejecuci\'on del ciclo, \texttt{mesetaMaxima} contiene la cantidad de v\'ertices m\'as grande dentro de las cantidades de v\'ertices
	de las mesetas m\'aximas vistas.
\end{lemma}

\begin{proof}
	Inicialmente el valor de mesetaMaxima es cero, menor al de todas las posibles cantidades de v\'ertices de una meseta m\'axima (puesto que como ya demostramos,
	la m\'inima cantidad de elementos de una meseta de una celda $c$ es una puesto que $\{ c \}$ es una meseta v\'alida, y una meseta m\'axima es la que m\'as
	v\'ertices contiene). Esto se corresponde con el hecho de que ninguna meseta m\'axima ha sido examinada por ahora.
	
	Cuando en el ciclo \texttt{for} encontramos una celda no visitada, expandimos llamando a \texttt{contar}. Como ya demostramos en un lema anterior, al
	inicializar \texttt{mesetaActual} a 1, esto implica que \texttt{mesetaActual} se corresponde con la cantidad de veces que fue llamada la funci\'on \texttt{contar} 
	en esa iteraci\'on del \texttt{for} de resolver (incluyendo las recursivas). Como por cada iteraci\'on del cuerpo interno del \texttt{for} se llama a \texttt{contar}
	tantas veces como la cantidad de v\'ertices de la meseta m\'axima de la celda por la cual empezamos a propagar, entonces despu\'es de la llamada a \texttt{contar},
	\texttt{mesetaActual} tiene la cantidad de celdas dentro de la meseta m\'axima de $c$. Al actualizar \texttt{mesetaMaxima} por el m\'aximo entre las dos \texttt{mesetaActual},
	mantengo el invariante de que \texttt{mesetaMaxima} es la cantidad de v\'ertices m\'axima de las mesetas m\'aximas ya vistas (puesto que si \texttt{mesetaActual} es m\'as grande
	que \texttt{mesetaM\'axima}, la meseta reci\'en vista es la que contiene m\'as v\'ertices hasta ahora).
	
	Como inicialmente el valor de \texttt{mesetaMaxima} es m\'as chico que el valor de cualquier posible cantidad de v\'ertices de una meseta m\'axima, eso nos
	asegura que sera pisado por el valor de la primer meseta m\'axima encontrada.
	
	Combinando estas dos proposiciones se tiene lo que se quer\'ia demostrar. \qed
\end{proof}

Y ahora si, ya tenemos todo como para mostrar que

\begin{theorem}
	El algoritmo propuesto es correcto.
\end{theorem}

\begin{proof}
	Puesto que \texttt{mesetaMaxima} contiene en todo momento del ciclo la cantidad de v\'ertices m\'as grande de las mesetas m\'aximas vistas, y como
	el algoritmo visita cada meseta m\'axima de la matriz una vez, entonces al finalizar el ciclo \texttt{mesetaMaxima} contendra la m\'axima cantidad de celdas
	de alguna de las mesetas m\'axima vistas. \qed
\end{proof}

Al lector que este interesado, puede demostrarse que el problema propuesto es equivalente al problema de encontrar la c\'antidad de v\'ertices m\'axima para
todas las componentes conexas de un grafo. En este caso el grafo $G = (V,E)$ que nos interesa tiene como conjunto $V$ a las celdas de la matriz, y como $E$
a los pares de celdas $c, c'$ tales que $c$ y $c'$ son directamente adyacentes y tienen el mismo valor. El algoritmo presentado es una modificaci\'on del
algoritmo DFS (Depth-First Search) para este caso particular.~\cite{cormen}.

\subsection{Complejidad de los algoritmos}

El algoritmo propuesto tiene complejidad $O(nm)$ temporal y espacial, siendo $n$ y $m$ las dimensiones de la matriz.
Para ello, explicitamos la implementaci\'on de las operaciones \texttt{marcar} y \texttt{visitada}, entre otras.

\begin{algorithm}[H]
	\caption{Pseudoc\'odigo para combinar dos arreglos ordenados $A$ y $B$ en un 
	arreglo ordenado $C$.}
	\label{algo::contar_mesetas_posta}
	\begin{algorithmic}
%		\State \Comment{Las celdas se representan como pares $(i,j)$ de enteros. }
		\Statex
%		\State \Comment{Variables globales}
		
		\State \Var tablero %\Comment{Tablero con los valores de la casilla}
		\State \Var visitada %\Comment{Matriz booleana, el valor corresponde a si la celda $(i,j)$ esta marcada o no.}
		\State \Var mesetaActual,mesetaMaxima
		\Statex
%		\State \Comment{celdasVecinas: devuelve la celdas adyacentes a la pasada por parametro}
		\Function{celdasVecinas}{Celda $(i,j)$}
			\State vecinas $\gets []$
			\For{$(p,q) \in \{(i,j+1),(i,j-1),(i+1,j),(i-1,j)\}$}
				\If{$p \geq 0 \wedge p < \# filas(tablero) \wedge q \geq 0 \wedge q < \# columnas(tablero)$}
					\State agregar(vecinas, $(p,q)$)
				\EndIf
			\EndFor
			\State \Return vecinas
		\EndFunction
		\Statex
%		\State \Comment{contarMeseta: Dada una casilla $(i,j)$, calcula el tama\~no de la meseta m\'axima que la contiene, propagando recursivamente.}		
		\Function{contar}{Celda $(i,j)$}
			\ForAll{$(p,q) \in celdasVecinas(tablero,(i,j)$}
				\If{ valor(tablero,$(p,q)$) = valor(tablero, $(i,j)$) $\wedge \neg$ visitada[$(p,q)$)] }
%					\State \Comment{Esto quiere decir que la casilla $(p,q)$, al ser vecina de $(i,j)$ es parte de la meseta que contiene a $(p,q)$. La contamos
%					si no la hemos visitado anteriormente, y propagamos a sus vecinas no visitadas con igual valor (que son parte de la isla tambi\'en).}
					\Statex
					\State $visitada[(p,q)] = \True$
					\State $mesetaActual \gets mesetaActual + 1 $
				
%					\State \Comment{Continuo propagando desde esta casilla para calcular la meseta}
					\Statex
					\State contarMeseta($(p,q)$)
				\EndIf
			\EndFor
		\EndFunction

%		\State \Comment{resolver: Resuelve el ejercicio en si, llamando a contar para todas las casillas}
		\Function{resolver}{t}
			\State tablero $\gets$ t
			\State mesetaMaxima $\gets$ 0

			\ForAll{$(i,j)$ $\in$ casillas(tablero)}
				\If{$\neg$ visitada[$(i,j)$]}
					%\State \Comment{Si no visite esta casilla entonces su meseta no esta calculada. La calculo usando contar. }
					\Statex
					\State visitada[$(i,j)$] = \True
					\State mesetaActual = 1, valorActual = valor(tablero,$(i,j)$) %\Comment{En mesetaActual guardo el tama\~no del pedazo de meseta propagado, que al principio es una casilla. } 
				
					\State contar($(i,j)$)
					
%					\State \Comment{Ya terminamos de propagar la meseta de la casilla $(i,j)$.}
					\Statex
					\State mesetaMaxima $\gets \max$(mesetaMaxima, mesetaActual);
				\EndIf
			\EndFor
			
			\State \Return mesetaMaxima 

		\EndFunction
		
	\end{algorithmic}
\end{algorithm}

Podemos asegurar que las implementaciones de las operaciones de \texttt{marcar} y \texttt{visitada} son
$O(1)$ puesto que usamos para ello una matriz de booleanos, lo cual nos da tiempo de acceso a un elemento
$O(1)$.

Podemos asegurar que la cantidad de operaciones ejecutadas dentro de \texttt{contar}, desconsiderando las llamadas
recursivas, son $O(1)$, puesto que el ciclo \texttt{for} corre una cantidad de veces acotada a priori (puesto que en una matriz,
una celda solo puede tener hasta 4 vecinas), y conseguir la lista de vecinas de una celda tambi\'en toma $O(1)$ porque implica
una cantidad acotada de inserciones en una lista. Dentro de cada ejecuci\'on del for, adem\'as de la llamada recursiva, tenemos
una cantidad finita de operaciones $O(1)$, porque consisten en operaciones aritm\'eticas, de comparaci\'on, accesos a la matriz
\texttt{visitada}, etc. Todas las cuales se pueden hacer en $O(1)$. 

Veamos que el total de llamadas a \texttt{contar} es $O(nm)$. Esto se ve f\'acilmente del hecho de que, como demostramos
en un lema anterior, para una celda dada $c$ la cantidad de llamadas a \texttt{contar} que implica \texttt{contar(c)} es igual
a la cantidad de celdas dentro de la meseta m\'axima de $c$. Tambi\'en demostramos en un lema anterior que toda meseta m\'axima
es recorrida una \'unica vez, puesto que el ciclo principal de \texttt{resolver}, cada vez que encuentra una celda no visitada, expande y marca
todas las celdas de su meseta m\'axima, y esto implica que toda celda de una meseta m\'axima es visitada una vez. Como toda celda pertence a una y solo
una meseta m\'axima, la suma de la cantidad de celdas de cada meseta m\'axima de la matriz es igual a la cantidad de celdas de la matriz, $O(nm)$.

Tenemos entonces que llamamos a \texttt{contar}, una cantidad $O(nm)$ veces. Como las operaciones exceptuando las llamadas recursivas son $O(1)$, en total
tenemos un $O(nm)$. Puesto que mantenemos que casillas fueron visitadas, en el ciclo principal de \texttt{resolver} solo entramos dentro del cuerpo del \texttt{if}
si la celda no fue ya visitada, lo cual como ya demostramos corresponde a cuando su meseta m\'axima no fue ya propagada y marcada. Para esto requerimos tambi\'en
que iterar todas las celdas de la matriz sea $O(nm)$, lo cual como veremos m\'as adelante es posible en la implementaci\'on realizada.

Por lo tanto, si aseguramos que las operaciones mencionadas son $O(1)$, incluyendo las asignaciones del tablero por ejemplo, la complejidad obtenida es entonces
$O(nm)$.

\subsection{Detalles de la implementaci\'on en Java}

La implementaci\'on consiste en un conjunto de clases, Las clases \texttt{Celda}, \texttt{Matriz} y \texttt{Ejercicio2}. La clase
\texttt{Celda} nos permite mantener todas las operaciones relacionadas con la matriz en una misma clase, mejorando la modularidad de la soluci\'on. Por ejemplo,
para delegar la responsabilidad de mantener si una casilla ya fue visitada y marcarla, tenemos un m\'etodo \texttt{marcar} y \texttt{fueVisitada}.

\texttt{Matriz} mantiene una matriz de celdas, y nos permite por ejemplo obtener las vecinas de una matriz en $O(1)$ al utilizar una lista enlazada \texttt{LinkedList}
como container para devolver las celdas vecinas. La lista ordenada \texttt{LinkedList} en Java tiene $O(1)$ costo por inserci\'on y se puede iterar en un tiempo en 
el \'orden de su longitud, por lo tanto la utilizamos posteriormente en el cuerpo de \texttt{contarMeseta} para iterar sobre todas las celdas vecinas de la
pasada por par\'ametro en $O(1)$ (porque la cantidad de celdas directamente adyacentes de una celda esta acotada por 4).

Para iterar todas las casillas, creamos un iterador como una clase interna de \texttt{Matriz}. Este iterador nos permite conseguir la pr\'oxima casilla a
iterar en $O(1)$, por lo tanto nos permite iterar todas las casillas del tablero en $O(1)$. Al devolver una referencia a \texttt{Celda}, devolver la celda
actual es $O(1)$. La raz\'on por la cual podemos devolver la referencia a la celda teniendo su posici\'on, es porque el iterador se implementa como una
clase interna. Una instancia de una clase interna en java se instancia solamente a partir de una instancia de la clase que la contiene, y la clase interna
tiene acceso a todos los atributos de la clase que la contiene. Por lo tanto, el iterador tiene acceso a la matriz de celdas del tablero a partir del cual
lo instanciamos.

El iterador implementado es una implementaci\'on de la interfaz \texttt{Iterable<Celda>}, que nos permite utilizar la siguiente notaci\'on:

\begin{verbatim}
	for(Celda c : vecinas)
\end{verbatim}

para iterar sobre las vecinas, que consiste en \textit{syntatic sugar} que java provee.

Lo que hace este iterador es simplemente continuar mirando la pr\'oxima celda en la fila actual. Si ya terminamos con la fila, seguimos
con la siguiente. Como las operaciones involucradas para realizar esto es una cantidad constante de asignaciones y operaciones de tipos primitivos del lenguaje,
la complejidad es por lo tanto $O(1)$.

Como ya marcamos en el ejercicio anterior, tambi\'en tenemos que las asignaciones son $O(1)$, puesto que en Java toda variable es de un tipo primitivo, o una
referencia a un objeto, o sea un puntero a una instancia de la clase (lo cual toma $O(1)$ en copiar). El pasaje de par\'ametros es entonces $O(1)$ en Java.

Finalmente entonces, excepto por estos detalles espec\'ificos de la implementaci\'on en Java, el algoritmo implementado es id\'entico al presentado
en las secciones anteriores.

\subsection{Resultados}

\subsection{Conclusiones}
